﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FrogEngine
{
	public class HeapTree<K, V> 
		where K : IComparable
	{
		public HeapTree()
		{
			tree = new List<IBinaryTreeNode<K, V>>();
			map = new Dictionary<V, IBinaryTreeNode<K, V>>();
			tree.Add(null);
		}

		private List<IBinaryTreeNode<K, V>> tree;
		Dictionary<V, IBinaryTreeNode<K, V>> map;

		private IBinaryTreeNode<K, V> root;
		public IBinaryTreeNode<K, V> Root
		{
			get { return root; }
			set { root = value; }
		}

		public IBinaryTreeNode<K, V> Add(K key, V value)
		{
			var node = new BinaryTreeNode<K, V>(null, key, value);
			tree.Add(node);
			map.Add(node.Value, node);
			if (tree.Count > 2)
			{
				var parent = tree[(tree.Count - 1) / 2];
				node.Parent = parent;
				if (tree.Count % 2 == 0)
					parent.Right = node;
				else
					parent.Left = node;
			}
			else
				Root = node;
			return node;
		}

		public IBinaryTreeNode<K, V> Remove()
		{
			var node = tree[tree.Count - 1];
			tree.RemoveAt(tree.Count - 1);
			map.Remove(node.Value);
			return node;
		}

		public IBinaryTreeNode<K, V> GetNode(V key)
		{
			return map[key];
		}

		public bool Contains(V item)
		{
			return map.ContainsKey(item);
		}

		public K GetKey(V key)
		{
			return map[key].Key;
		}

		public bool IsEmpty
		{
			get { return tree.Count == 1; }
		}

		public int Size
		{
			get
			{
				return tree.Count - 1;
			}
		}

		private IBinaryTreeNode<K, V> Sibling(IBinaryTreeNode<K, V> node)
		{
			if (node.Parent != null)
			{
				if (node == node.Parent.Left)
					return node.Parent.Right;
				else
					return node.Parent.Left;
			}
			return null;
		}

		public IBinaryTreeNode<K, V> RightChild(IBinaryTreeNode<K, V> node)
		{
			return node.Right;
			//int index = tree.IndexOf(node);
			//try
			//{
			//    var rchild = tree[index * 2 + 1];
			//    return rchild;
			//}
			//catch
			//{
			//    return null;
			//}
		}

		public IBinaryTreeNode<K, V> LeftChild(IBinaryTreeNode<K, V> node)
		{
			return node.Left;
			//int index = tree.IndexOf(node);
			//try
			//{
			//    var lchild = tree[index * 2];
			//    return lchild;
			//}
			//catch
			//{
			//    return null;
			//}
		}

		public void Swap(IBinaryTreeNode<K, V> n1, IBinaryTreeNode<K, V> n2)
		{
			K tempK;
			V tempV;
			tempK = n1.Key;
			tempV = n1.Value;
			n1.Key = n2.Key;
			n1.Value = n2.Value;
			n2.Key = tempK;
			n2.Value = tempV;
		}

		public void Replace(IBinaryTreeNode<K, V> n1, IBinaryTreeNode<K, V> n2)
		{
			n1.Key = n2.Key;
			n1.Value = n2.Value;
		}

		public void BuildHeap()
		{
			int count = tree.Count - 1;
			if (count > 0)
				for (int i = count / 2; i >= 1; i--)
					Heapify(tree[i]);
		}

		public void Heapify(IBinaryTreeNode<K, V> i)
		{
			var l = i.Left;
			var r = i.Right;
			IBinaryTreeNode<K, V> smallest;
			if (l != null && Comparer<K>.Default.Compare(l.Key, i.Key) < 0)
				smallest = l;
			else
				smallest = i;
			if (r != null && Comparer<K>.Default.Compare(r.Key, smallest.Key) < 0)
				smallest = r;
			if (smallest != i)
			{
				Swap(i, smallest);
				Heapify(smallest);
			}
		}

		//private void Heapify(IBinaryTreeNode<K, V> node)
		//{
		//    while (heapTree.LeftChild(node) != null)
		//    {
		//        var s = heapTree.RightChild(node);
		//        if (s == null || Comparer<K>.Default.Compare(heapTree.LeftChild(node).Key, s.Key) <= 0)
		//        {
		//            s = heapTree.LeftChild(node);
		//        }
		//        if (Comparer<K>.Default.Compare(s.Key, node.Key) < 0)
		//        {
		//            heapTree.Swap(node, s);
		//            node = s;
		//        }
		//        else break;
		//    }
		//}
	}

	public class BinaryHeap<K, V>
		where K : IComparable
	{
		public BinaryHeap()
		{
			heapTree = new HeapTree<K, V>();
		}

		private HeapTree<K, V> heapTree;

		public void InsertItem(K key, V value)
		{
			var z = heapTree.Add(key, value);
			while (z != heapTree.Root)
			{
				var u = z.Parent;
				if (Comparer<K>.Default.Compare(u.Key, z.Key) <= 0)
					break;
				heapTree.Swap(u, z);
				z = u;
			}
		}

		public void RemoveMin()
		{
			if (heapTree.Size == 1)
				heapTree.Remove();
			else
			{
				var last = heapTree.Remove();
				heapTree.Replace(heapTree.Root, last);
				heapTree.Heapify(heapTree.Root);
			}
		}

		public V MinElement()
		{
			return heapTree.IsEmpty ? default(V) : heapTree.Root.Value;
		}

		public K MinKey()
		{
			return heapTree.IsEmpty ? default(K) : heapTree.Root.Key;
		}

		public bool ContainsElement(V item)
		{
			return heapTree.Contains(item);
		}

		public void ChangeKey(V item, K newKey)
		{
			var node = heapTree.GetNode(item);
			node.Key = newKey;
			heapTree.BuildHeap();
		}

		public K GetKey(V value)
		{
			return heapTree.GetKey(value);
		}

		public int Size
		{
			get { return heapTree.Size; }
		}

		public bool IsEmpty
		{
			get { return heapTree.IsEmpty; }
		}
	}
}
